public class CoinChange{
	public static int countSolutions(int S[], int m, int n)
	{
		int x, y;
		int[][] table = new int[n+1][m];
		for(int i = 0; i < m; i++)
		{
			table[0][i] = 1;
		}

		for(int i = 1; i < n+1; i++)
		{
			for(int j = 0; j < m; j++)
			{
				//including
				x = (i-S[j]>=0)?table[i-S[j]][j]:0;
				//excluding
				y = (j >= 1)?table[i][j-1]:0;

				table[i][j] = x + y;

			}

		}

		return table[n][m-1];
	}


	public static void main(String[] args) {
		int[] S = {1,2,3};
		int n = 4;
		int m = 3;
		System.out.println(countSolutions(S,m,n));
	}
}